This invention relates to a system adapted for the automatic detection and correction of errors occurring in digital data transmission or storage and more particularly to the system of the type designed to operate upon a data bit train (sequence) received in parallel for the error detection and correction.
The principles of error detection and correction will now be explained conveniently in connection with data transmission.
As is known in the art, most of errors occurring in the data transmission are caused by the noise on the transmission channel. In order to avoid the adverse effects of noise, conventional error detection and/or correction systems have been employed in which, at the transmitter, a train of information bits is sent out onto the transmission channel, together with a train of redundant bits and, at the receiver, the received bit train is decoded on the basis of the redundancy of the code formation.
A well-known method of adding the train of the redundant bits is to employ a cyclic error-correcting code such as that described by SHU Lin in the book titled, An Introduction to Error Correcting Codes, pp. 70-77, published in 1970 by Prentice-Hall, Inc., Englewood Cliffs, N.J.
To describe this method briefly, a train of redundant bits a.sub.k+1, a.sub.k+2, . . . , a.sub.k+m to be added to a train of information bits a.sub.1, a.sub.2, . . . , a.sub.k is determined as follows: Namely, a polynomial I(x) = a.sub.1 x.sup.N-1 + a.sub.2 x.sup.N-2 + . . . + a.sub.k x.sup.N-k, which corresponds to the information bit train, N(=k+m) representing the code length or the combined length of the two (information and redundant) bit trains, is divided by a predetermined generator polynomial of degree m, g(x) = x.sup.m + g.sub.1 x.sup.m-1 + . . . + g.sub.m-1 x + 1 to obtain a remainder polynomial R(x) = r.sub.1 x.sup.m-1 + r.sub.2 x.sup.m-2 + . . . + r.sub.m-1 x + r.sub.m. Then, the redundant bits a.sub.k+1, a.sub.k+2, . . . , a.sub.k+m are determined as the coefficients of the remainder polynomial r.sub.1, r.sub.2, . . . , r.sub.m, respectively. It is to be noted that a code polynomial A(x) = a.sub.1 x.sup.N-1 + a.sub.2 x.sup.N-2 + . . . . a.sub.N-1 x + a.sub.N representing a combination of the trains, of the information bits and the redundant bits determined in the manner described above is at all times divisible by the generator polynomial g(x) of degree m.
On the other hand, at the receiver, the code formed in the manner described above is received, and the polynomial A(x) representing the received code is divided by the generator polynomial g(x) for error detection. As a result, it is decided that the received code is correct when there is no remainder produced in the division and that in error when there is given any remainder. The received bit or bits to be corrected are then identified depending on the bit pattern of the remainder and properly corrected. The decoder or the processing circuit used for this purpose is comprised of a feedback shift register for effecting the division by g(x), a bit-pattern detector and a buffer memory so as to normally operate upon the received code serially by bits. Such a serial processing circuit, however, must be converted into one for use with parallel data in case where the data should be dealt with in groups of eight bits, i.e., in characters, or at speed slower than the serial data speed.
A decoder designed to operate in parallel upon a cyclic error-correcting code and already put into practical use is seen in the U.S. Pat. No. 3,452,328, which describes the device including a parallel-input parallel-feedback type shift register 16 (FIG. 1), a detector 18 for detecting a number of bit patterns, and a buffer memory 12 for storing received data. In the shift register 16, the pattern of feedback connections is determined depending on the number u of parallel input lines, and the generator polynomial g(x). In other words, the feedback connections are made so that the contents in the shift register 16 after the supply of one clock pulse represent the result obtained upon operation of the corresponding serial processing circuit in a period of u consecutive clocks.
As a disadvantage of this decoder, the increase of the number of parallel input bits or the complicated structure of the generator polynomial invites the increase of the number of gates included between individual registers in the shift register 16, and, in some cases, this makes it difficult to attain any desired reduction in processing speed, which is one of the major objects of parallelization.
Generally, in the case where reduction in the data transmission speed is required due to deterioration in performance of the transmission line, it is desirable to change the number of parallel input bits at the receiver so that the operating clock for the decoder (the whole structure shown in FIG. 1 of the U.S. Pat. No. 3,452,328) may remain unchanged. In such a case, however, it will be apparent that the parallel-processing system of the U.S. Pat. No. 3,452,328 cannot be utilized as it stands. Therefore, there arises the need for remodelling the network according to the change required in the number of parallel input bits. Thus, the system of the U.S. patent lacks the adaptability.